The present inventive concepts relate to key value stores, and more particularly, to a system and method for efficiently handling key collisions when accessing data in a key value store.
A key value store is a type of computer database that can be used in data-intensive, high-performance, scale-out computing environments. Key value stores allow computer applications to store schema-less data. Schema-less data can include structures having a string that represents the key and the actual data that is considered the value in a “key-value” relationship. Such key-value structures replace the need for fixed data models and also allow for proper formatting.
Key value stores consider a flash memory device or a solid state disk/drive (SDD) as a block device. Thus, a key value store maintains its own mapping which, in many cases, can be redundant to mappings maintained by a Flash Translation Layer (FTL) of the flash memory or SDD. Conventionally, the mapping maintained by the key value store includes the actual key. This is needed to check for hash collisions and key over-write scenarios (unless a key value store library sacrifices an I/O for this purpose). But keeping all of the keys in memory requires significant memory. On the other hand, issuing extra I/Os to read a key degrades performance. For example, in case of hash collisions, on writes, the key can be rehashed and mapped to a new logical block address (LBA). However, such remapping effort fails if the same key is being over-written. On reads, the key value library might need to issue multiple reads and validate the requested key with the actual key stored on non-volatile media before returning the value associated with the requested key. Embodiments of the present inventive concept address these and other limitations in the prior art.